/**
 * This file is part of Graph-Tool.
 * 
 * Graph-Tool is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * Graph-Tool is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * Graph-Tool. If not, see <http://www.gnu.org/licenses/>.
 */
package graphtool.graphs.algorithms.directed;

import graphtool.graphs.DirectedGraph;
import graphtool.graphs.GraphPropertyException;
import graphtool.math.matrices.IndexException;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Vector;

import org.apache.log4j.Logger;

/**
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 * 
 */
public final class Dijkstra<V, E>
{

  /**
   * Stores the processing results of the predecessors.
   */
  private HashMap<V, V> _preDecessors = new HashMap<V, V>();

  /**
   * Distance between the nodes
   */
  private HashMap<V, Float> _distance = new HashMap<V, Float>();

  /**
   * Set of unvisited nodes
   */
  private Vector<V> _unvisited = new Vector<V>();

  /**
   * The graph object
   */
  private DirectedGraph<V, E> _graph = null;

  /**
   * The node the algorithm is starting from
   */
  private V _start = null;

  /**
   * Internal logger object
   */
  private Logger _logger = Logger.getLogger( Dijkstra.class );

  /**
   * Constructor of class
   * 
   * @param graph
   * @param start
   * @throws GraphPropertyException
   */
  public Dijkstra( DirectedGraph<V, E> graph, V start )
      throws GraphPropertyException
  {
    this._graph = graph;
    this._start = start;

    initialize();

    try
    {
      dijkstra();
    }
    catch( IndexException ie )
    {
      throw new GraphPropertyException( ie );
    }
  }

  /**
   * Initialize the internal states as described by Dijkstra
   */
  protected void initialize()
  {
    for( V node : _graph.getVertices() )
    {
      _distance.put( node, Float.MAX_VALUE );
      _preDecessors.put( node, null );

      if( node.equals( _start ) )
      {
        _distance.put( node, (float) 0 );
      }
    }
    // Patch
    _unvisited.add( _start );
  }

  /**
   * Make distance update as described by Dijkstra
   * 
   * @param u
   *          - Start node
   * @param v
   *          - Target node
   */
  protected void distanceUpdate( V u, V v )
  {
    Float abstand_u = _distance.get( u );
    Float abstand_v = _distance.get( v );

    // find corresponding edge weights
    Collection<E> ce = _graph.getEdges();

    Iterator<E> edges = ce.iterator();

    Float distance_uv = Float.MAX_VALUE;

    while( edges.hasNext() )
    {
      E edge = edges.next();

      if( _graph.getSource( edge ).equals( u ) && _graph.getTarget( edge ).equals( v ) )
      {
        distance_uv = _graph.getEdgeWeight( edge );
        break;
      }
    }

    // No edge with the tested direction found
    if( distance_uv == Float.MAX_VALUE )
      return;

    Float alternative = abstand_u + distance_uv;

    _logger.debug( "Abstand u: " + abstand_u );
    _logger.debug( "Abstand v: " + abstand_v );
    _logger.debug( "Abstand uv: " + distance_uv );
    _logger.debug( "Alternative: " + alternative );

    if( alternative < abstand_u + abstand_v )
    {
      _logger.debug( "Setze neuen Abstand zwischen Knoten: " + _start + " zum Knoten v: " + v + " mit Wert: " + alternative );

      _distance.put( v, alternative );
      _preDecessors.put( v, u );
    }
  }

  /**
   * Internal helper function returning the shortest path. It makes use of an
   * backward iterator in order to provide the shortest path between source and
   * target.
   * 
   * @param target
   * @return
   * @throws GraphPropertyException
   * @throws IndexException
   */

  public DirectedGraphPath<V, E> getShortestPath( V target ) throws GraphPropertyException,
      IndexException
  {
    DirectedGraphPath<V, E> _result = new DirectedGraphPath<V, E>( _start );

    V u = target;

    LinkedList<V> path = new LinkedList<V>();

    path.add( target );

    _result.addNode( target );

    while( _preDecessors.containsKey( u ) )
    {
      V temp = u;

      u = _preDecessors.get( u );

      if( null != u )
      {
        path.add( u );
    
        _result.addNode( u );

        E e = _graph.findEdge( u, temp );
        _result.addEdge( e, u, temp );
      }
    }

    if( !path.getLast().equals( _start ) )
      return null;

    Collections.reverse( path );

    return _result;
  }

  /**
   * Returns the node with the minimum distance value assigned
   * 
   * @return Vertex with the minimal distance value
   */
  protected V getMinimumDistance()
  {
    V minimum = null;

    for( V vertex : _unvisited )
    {
      if( minimum == null )
      {
        minimum = vertex;
      }
      else
      {
        if( null != _distance && _distance.get( vertex ) < _distance.get( minimum ) )
        {
          minimum = vertex;
        }
      }
    }
    return minimum;
  }

  /**
   * Implementation of Dijktra Algorithm
   * 
   * @throws IndexException
   */
  protected void dijkstra() throws IndexException
  {
    while( !_unvisited.isEmpty() )
    {
      V u = getMinimumDistance();

      _logger.debug( "minimum distance node: " + u );

      _unvisited.remove( u );

      Collection<V> neighbours = _graph.neighbours( u );

      for( V neighbour : neighbours )
      {
        if( !_preDecessors.containsValue( neighbour ) && (_graph.findEdge( u, neighbour ) != null) )
        {
          if( neighbour != _start )
            _unvisited.add( neighbour );
        }
      }

      dumpUnvisited( _unvisited );

      for( V neighbour : neighbours )
      {
        if( _unvisited.contains( neighbour ) )
        {
          distanceUpdate( u, neighbour );
        }
      }
    }
  }

  

  /**
   * Helper function dumping the current list of unvisited nodes
   * 
   * @param unvisited
   */
  protected void dumpUnvisited( Vector<V> unvisited )
  {
    for( V v : unvisited )
    {
      _logger.debug( "Unvisited node: " + v );
    }
  }
}
